package com.salim.leetcode.$40;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSumII {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        loop(new ArrayList<>(),candidates,0,target,result);
        return result;
    }

    public void loop(List<Integer> currentList,int[] candidates,int sum,int target,List<List<Integer>> result){
        for(int i=0;i<candidates.length;i++){
            //重复跳过
            if(i>0 && candidates[i] == candidates[i-1]){
                continue;
            }
            if(sum+candidates[i] == target){
                currentList.add(candidates[i]);
                result.add(currentList);
                break;
            }
            if(sum+candidates[i]>target){
                break;
            }
            if(sum+candidates[i]<target){
                List<Integer> next = new ArrayList<>(currentList);
                next.add(candidates[i]);
                if(i+1<candidates.length){
                    loop(next, Arrays.copyOfRange(candidates,i+1,candidates.length),sum+candidates[i],target,result);
                }
            }
        }
    }
}
